package com.demo.datastructure.reorder.quickSort;

/**
 * @description: 通过快速排序找到第n大元素
 * @author: ljr
 * @time: 2021/5/4 18:02
 */
public class MyQuickSort2 {


    public static void quickSort(int[] args, int n, int element){
        quickSortC(args,0,n-1,element);
    }

    private static void quickSortC(int[] args, int p, int r,int element) {
        if(p >= r) return;
        int q = partition(args,p,r);
        if(args[q] == element){
            return;
        }else if(q < element){
            quickSortC(args,q+1,r, element);
        }else{
            quickSortC(args,p,q-1,element);
        }

    }

    private static int partition(int[] args, int p, int r) {
        int pivot = args[r];
        int i = p;
        int j = p;
        for(; j < r; j++){
            if(args[j] < pivot){
                int val = args[i];
                args[i] = args[j];
                args[j] = val;
                i++;
            }
        }
        int val =  args[i];
        args[i] = args[r];
        args[r] = val;
        return i;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{11,8,3,9,7,1,2,5};
        //找出第3大元素
        MyQuickSort2.quickSort(nums,8, 8-3);

        System.out.println(nums[8-3]);

    }
}
